package leetcode_1001_1100;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_1039_3 {
    public static void main(String[] args) {

    }

    int n;
    int[] values;
    Map<Integer, Integer> memo = new HashMap<>();

    private int minScoreTriangulation(int[] values) {
        n = values.length;
        this.values = values;
        return dp(0, n - 1);
    }

    private int dp(int i, int j) {
        if (i + 2 > j)
            return 0;
        if (i + 2 == j)
            return values[i] * values[i + 1] * values[i + 2];
        int key = i * n + j;
        if (!memo.containsKey(key)) {
            int minMemo = Integer.MAX_VALUE;
            for (int k = i + 1; k < j; k++) {
                minMemo = Math.min(minMemo, values[i] * values[j] * values[k] + dp(i, k) + dp(k, j));
            }
            memo.put(key, minMemo);
        }
        return memo.get(key);
    }
}
